package 剑指offer;

public class 面试题40最小的k个数 {
    public static void main(String[] args) {
        int[] arr = {3,2,1,0};
        面试题40最小的k个数 o = new 面试题40最小的k个数();
        int[] ints = o.getLeastNumbers(arr, 1);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        //快排
        int[] nums = new int[k];
        qiuckSort(arr,0,arr.length-1);
        for(int i = 0;i < k;i++){
            nums[i] = arr[i];
        }
        return nums;
    }

    private void qiuckSort(int[] arr,int l,int r){
        if(l >= r) return;
        int p = help(arr,l,r);
        qiuckSort(arr,l,p-1);
        qiuckSort(arr,p+1,r);
    }
    private int help(int[] arr,int l,int r){

        int tem = arr[l];
        int j = l;//小于tem得范围[l+1,j],初始化j等于l；前闭后闭，表示没有没有元素
        //j+1到i得位置表示大于tem得元素
        //i表示当前位置得值
        for(int i = l+1;i <= r ; i ++){
            if(arr[i] < tem){
                //如果当前位置元素比tem小,交换j和i得位置，j++，此时[l,j]得位置依旧是小于tem
                swap(arr,j+1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }
    void swap(int[] arr,int i ,int j){
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
}
